package com.mzy.linear_struct;


import java.util.*;

/**
 * @Author: codermzy
 * @Date: 2024/04/12/15:44
 * @Description:
 */
public class Graph<T> {

    // 顶点
    private final List<T> vertexes = new ArrayList<>();

    // 边
    private final Map<T, List<T>> adjList = new HashMap<>();


    public void addVertex(T vertex) {
        vertexes.add(vertex);
        adjList.put(vertex, new ArrayList<>());
    }

    public void addEdge(T v1, T v2) {
        adjList.get(v1).add(v2);
        adjList.get(v2).add(v1);
    }


    public void traver() {
        vertexes.forEach(vertex -> {
            List<T> edges = adjList.get(vertex);
            StringJoiner joiner = new StringJoiner(", ");
            for (T edge : edges) {
                joiner.add((String) edge);
            }
            System.out.println(vertex + "->" + joiner);
        });
    }

    public void bst() {
        if (vertexes.isEmpty()) return;
        Queue<T> queue = new LinkedList<>();
        queue.offer(vertexes.get(0));

        Set<T> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            T t = queue.poll();
            visited.add(t);
            System.out.println(t);
            List<T> neighbors = adjList.get(t);

            for (T neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(t);
                }
            }
        }
    }

    public void dst() {
        if (vertexes.isEmpty()) return;

        Stack<T> stack = new Stack<>();

        HashSet<T> set = new HashSet<>();
        stack.push(vertexes.get(0));
        set.add(vertexes.get(0));
        while (!stack.isEmpty()) {
            T t = stack.pop();
            System.out.println(t);
            List<T> neighbors = adjList.get(t);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                if (!set.contains(neighbors.get(i))) {
                    set.add(neighbors.get(i));
                    stack.push(neighbors.get(i));
                }
            }
        }
    }


    public static void main(String[] args) {
        Graph<String> graph = new Graph<>();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F");
        graph.addVertex("G");
        graph.addVertex("H");
        graph.addVertex("I");
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("A", "D");
        graph.addEdge("C", "D");
        graph.addEdge("C", "G");
        graph.addEdge("D", "G");
        graph.addEdge("D", "H");
        graph.addEdge("B", "E");
        graph.addEdge("B", "F");
        graph.addEdge("E", "I");

        // graph.traver();
        // graph.bst();
        graph.dst();

        Scanner scan = new Scanner(System.in);
        int a = 0;
        int b = 0;
        while (scan.hasNextInt()){
            a = scan.nextInt();
            b = scan.nextInt();
        }

        System.out.println(a);
        System.out.println(b    );
    }
}
